Problem statement: zenit11kkg

g) (25 bodov) Učiteľ sa rozhodol obohatiť život svojim žiakom a zobral ich na filmový festival algoritmického programovania. Ako ale vysvitlo, na tomto festivale vznikol vážny problém pri organizácii a učiteľ so žiakmi bol požiadaný o pomoc pri jeho riešení. Organizátorom sa podarilo prenajať dve kinosály v multi extra ultra hyper 4D kinovom komplexe. Do programu bolo zaradených N (2 <= N <= 8) zaujímavých filmov. Každý z filmov má svoju celočíselnú dĺžku v minutach. Medzi filmami v kinosálach kvôli optimálne využitému času nebudú prestávky. Pre účastníkov je ale najlepšie, ked môžu medzi filmami zmeniť kinosálu, pretože nie každdého zaujíma každý film. Napríklad niektorých účastníkov nezaujímajú memoizácie backtrackov, ale nadovšetko ocenia najnovšie trendy v programovaní prehľadávaní grafov. Organizátori sa teraz pokúšajú zostaviť program v kinosálach : kde a kedy sa ktorý film bude premietať. Celý festival prebehne v jeden deň a premietanie sa začne v rovnakú minútu v oboch kinosálach. Chceme spraviť harmonogram premietania tak, aby existovalo čo najviac minút takých, že v danú minútu končia filmy v oboch kinosálach (vtedy sa dá pohodlne prejsť z jednej sály do druhej). Vo vstupnom súbore sa na prvom riadku nachádza počet vstupných sád (najviac 5). Každá vstupná sada pozostáva z dvoch riadkov. Na prvom z nich sa nachádza číslo N a na ďalšom riadku N medzerami oddelených čísel medzi 1 a 100 vrátane : dĺžky filmov v minútach. Pre každú testovaciu sadu vypíšte jeden riadok a na ňom text: Vstup X: Y, kde Y je odpoveď na príslušný testovací prípad. V tejto úlohe je časový limit 2 sekundy.

Príklad:

Vstup:

Výstup:

V prvom príklade sú dve možnosti: do prvej kinosály dať filmy s dĺžkami 10 a 30 (daná minúta bude 40.) alebo filmy s dĺžkami 20 a 10 (daná minúta bude 20., ak v druhej sále pôjde prvý film ten, ktorý má 20 minút).